Text of my article in Mathematics Teacher, Nov. 1988, Vol 81 # 8, 674-679. Note that "N2" means "N squared". MAGIC SQUARES OF ALL ORDERS Judson McCranie Introduction In an article in the Mathematics Teacher, Pizarro (1986) makes the statement that there seems to be no general procedures for generating magic squares of even orders. His mysterious statement is definitely false. Methods of construction for all orders have been known for decades. First, let's review some of the basic facts of magic squares. Most readers will already be familiar with these properties. A "magic square" is a square arrangement of the integers from 1 to N2, for order N (where N is a positive integer), such that the numbers in the cells of each column, each row, and each of the two main diagonals sum to the same number - called the constant of the magic square. The constant of a magic square of order N is N(N2+1)/2. Furthermore, magic squares exist for all positive orders, except in the case of N=2. This paper gives methods for constructing magic squares of all orders that can be adapted for use on a general-purpose electronic digital computer. A Pascal program for generating magic squares is included. The program was written in Turbo Pascal for IBM PCs and compatibles, but it should run on any Pascal system on any computer with no more than minor modifications. The only modification that is likely to be needed to run it on other systems is to reduce the size of the constant "maxorder" so the array called "cell" will fit into a small amount of memory. From a computability viewpoint alone, a brute-force check of all possible arrangements of the integers into a square constitutes a procedure to produce magic squares of any order. Although technically an algorithm, that approach is really not one that is considered tractable, since the number of possibilities grows at the rate of N factorial (N!). The number of possibilities would be too large to feasibly check for even moderately small values of N. The algorithms given here run in an amount of time that is a quadratic function of N, which is the best that can be expected since there are N2 cells to be filled. The program listed running on a Tandy 1000 generates an order 180 magic square in only about twelve seconds. Odd Orders When N is odd, we can use the method of S. de la Loubere as described in Ball and Coxeter (1947) and in Hunter and Madachy (1975). The method is simpler than the method of Dantzig that is given by Pizarro. Although Loubere's method only works for odd values of N, it is used in one of the methods of construction for even values of N. Let's number the columns from left to right and call the top row the first row, etcetera. Loubere's method is started by placing a 1 in the middle cell of the top row. The rest of the integers are inserted in order into the cells according to the following procedure. Generally, we continue along the diagonal toward the upper right. When this process would take us to the (nonexistent) zeroth row, continue with the Nth row instead. When it would take us to the (nonexistent) (N+1)th column, we continue on the first column instead. When we encounter a cell that has already been filled, we drop down one row below the cell we just filled, fill it, and continue diagonally from that cell. This could cause us to go to the (N+1)th row, in which case we go to the first row instead, analogously to the cases above. An order 5 magic square constructed by this method is shown in figure 1. The middle cell of the top row is filled with the integer 1. Then we continue along the diagonal to the upper right, however, this would carry us off of the square, so 2 is entered in the fifth row instead. Then 3 is entered on the diagonal to the right and above 2. Then we would move off of the square on the right, so 4 is entered in the first column. Then 5 is placed on the diagonal. The next integer would be placed along the diagonal, but that cell is already filled (with 1), so we drop down one cell (from the cell just filled) and continue. This process is continued until all cells are filled, and the result is a magic square. Even Orders In the case when N is even and N>2, we shall examine some methods in Ball and Coxeter. Hunter and Madachy seem to take their discussion of magic squares directly from this source, and their book may be easier to obtain. Unfortunately, their discussion of the case in which N is a multiple of 4 is rather ambiguous and it is not made clear how the procedure should be generalized for higher N. The former reference is clear, however. Let's call and even N singly-even if it is not divisible by 4 and call it doubly-even if it is divisible by 4. To motivate this terminology, note that singly-even integers are divisible by 2 only to the first power, whereas doubly-even integers are divisible by 2 to the second (or higher) power. Singly-Even N First, we shall consider the case where N is singly-even, that is N=6, 10, 14, etc. The following method is due to Ralph Strachey and is described by Ball and Coxeter and by Hunter and Madachy. The first step is to divide the N by N square into four sub-squares of size N/2 by N/2. Call the upper left sub-square A, the lower right B, the upper right C, and the lower left D. Now consider A an N/2 by N/2 square and use Loubere's method for order N/2 to construct a magic square in sub-square A. Then for each cell in sub-square B, set it equal to the sum of N2/4 and the value in the corresponding cell of A. For each cell in sub-square C, do the same, except add N2/2 to the value in the corresponding cell of A. The cells of D are filled in the same manner, except 3N2/4 is added to the corresponding cell of A. Now let M=(N-2)/4. Consider the middle row of A. Take the M cells after the first one and exchange them with the corresponding cells in D. For the other rows of A, take the first M cells of each row and exchange them with the corresponding cells of D. The final step is to exchange the cells in the M-1 rightmost columns of B with the corresponding cells of C. Figure 2 (parts a and b) shows how an order 10 magic square is constructed by this method. Figure 2a shows the square before the exchanges are made. Note that the upper left quadrant is the same as figure 1, the order 5 magic square constructed by Loubere's method. Figure 2b shows the resulting magic square. The method of exchanging makes it clear that each integer from 1 through N2 appears once and only once. Although the accompanying program uses the above method, it may be easier to use addition and subtraction rather than exchanges. Exchanging a cell in A with the corresponding cell in D can be effected by adding 3N2/4 to the cell in A and subtracting it from the cell in D. Exchanges between cells of B and C can be accomplished by adding N2/4 to the cell of B and subtracting it from the cell of C. Doubly-Even N Ball and Coxeter give an unnamed method for the case of doubly-even integers, that is N=4, 8, 12, etc. First, fill in the cells sequentially going left to right on the top row, then the second row, etc. So the first row will be the integers from 1 through N from left to right, the second row will contain N+1 through 2N from left to right, etcetera. Now divide the N by N square into (N/4)2 4 by 4 sub-squares. Now for each cell that is on the main diagonal of one of these sub-squares, exchange it with the cell that is symmetric to it with respect to the center of the N by N square. Figure 3 shows an order 8 magic square constructed this way. The method of exchanging makes it clear that each integer from 1 through N2 appears once and only once. From a computer programming standpoint, it is easier to replace the cells with its complement with respect to N2+1. That is, if the cell with I is to be exchanged, replace I by N2+1-I. This is clearly equivalent. Other Methods Ball and Coxeter (1947) and Hunter and Madachy (1975) also give some other methods of constructing magic squares, which will be mentioned here. The first is an alternative to Loubere's method for odd orders which is due to Bachet de Meziriac. It is the same as Loubere's method method, except for two details. The integer 1 goes in the cell just above the center cell. The diagonal insertion method continues until we reach an occupied cell. In this method, we jump up two rows instead of down one from the last cell that was filled. Note that this method, Loubere's method, and Dantzig's method all produce the familiar magic square of order 3, which is the only one of that order (except for rotations and reflections). Some readers may not satisfied by the fact that two methods are used for even orders, depending on whether N is divisible by 4 or not. The above sources also give a method that works for all even orders greater than 2 called de la Hire's method. It is a little more complex than the other methods and uses an auxiliary square in the construction, and it is not presented here. As far as I know, there is no single method that applies to both odd and even orders, except for the brute-force approach mentioned in the introduction. To be precise, the set of algorithms is closed under the union operation. So a program that applies one algorithm in some cases and another algorithm in other cases is itself an algorithm. I know of no effective methods that do not apply different cases, depending on the order. Also, note that there are magic squares that are not produced by any of these methods. Except for a few small orders, it is not known how many magic squares of a given order exist. There is no way I know of (except for brute-force methods) to produce all of the magic squares of a given order. ACKNOWLEDGMENTS Thanks to the reviewers who made suggestions that improved this paper. BIBLIOGRAPHY Ball, W. W. Rouse, and H. S. M. Coxeter. Mathematical Recreations and Essays. MacMillan, New York, 1947. Republished Dover, 1987. Hunter, J. A. H. and Joseph S. Madachy. Mathematical Diversions. Dover, New York, 1975. Pizarro, Antonio, "Computer-generated Magic Squares", Mathematics Teacher 79 (September 1986):471-76. ----------------end-of-author's-documentation--------------- Software Library Information: This disk copy provided as a service of The Public (Software) Library We are not the authors of this program, nor are we associated with the author in any way other than as a distributor of the program in accordance with the author's terms of distribution. Please direct shareware payments and specific questions about this program to the author of the program, whose name appears elsewhere in this documentation. If you have trouble getting in touch with the author, we will do whatever we can to help you with your questions. All programs have been tested and do run. To report problems, please use the form that is in the file PROBLEM.DOC on many of our disks or in other written for- mat with screen printouts, if possible. The P(s)L cannot de- bug programs over the telephone. Disks in the P(s)L are updated monthly, so if you did not get this disk directly from the P(s)L, you should be aware that the files in this set may no longer be the current versions. For a copy of the latest monthly software library newsletter and a list of the 2,000+ disks in the library, call or write The Public (Software) Library P.O.Box 35705 - F Houston, TX 77235-5705 (713) 665-7017